Hierarchical structures, such as logical tree structures, are known in many technical fields, and are employed to organize information in a logical form to facilitate storage and retrieval of the information. In a typical implementation, the highest node or “root” of the logical tree includes the most general information, with descendant nodes (i.e., child nodes, grandchild nodes, etc. moving away from the root node) providing additional detail as to a particular aspect of the information represented by the tree structure. It is, or course, desirable to navigate through the tree via the shortest path and/or in the shortest amount of time in order to store or retrieve information, and node traversal techniques for minimizing the time to perform these operations occupy engineers and scientists from a variety of different fields.
In the areas of graphics processing and rendering, ray tracing is a field which uses hierarchical structures for organizing information. Ray tracing involves a technique for determining the visibility of a primitive from a given point in space, for example, an eye, or camera perspective. Primitives of a particular scene which are to be rendered are typically located in nodes, and the nodes organized within a hierarchical tree. Ray tracing involves a first operation of “node traversal,” whereby nodes of the tree are traversed in a particular manner in an attempt to locate nodes having primitives, and a second operation of “primitive intersection,” in which a ray is intersected with one or more primitives within a located node to produce a particular visual effect. The operation of node traversal starts at a particular node or “entry point,” where a test is made to determine if the node contains any primitives. The node traversal process continues from the entry point to descendant nodes in the tree, to test additional nodes for the presence of primitives which may intersect a ray that is visible or that can create a visual effect within the scene.
In some conventional embodiments, the node traversal process commences at the root of the tree, i.e., at the highest rank, or most general level of the scene. In many instances, however, the root does not contain primitives which are intersected by a ray that produces a visible effect within the scene, and accordingly, skipping the root node and starting at a lower ranked node is typically more optimal in terms of minimizing the time required for the node traversal process.
FIGS. 1A and 1B illustrate an improvement of the aforementioned node traversal process, as described by A. Reshetov et al. in “Multi-Level Ray Tracing Algorithm,” Proc. SIGGRAPH 2005. The article describes a technique for identifying an entry point which is common to all primitive containing nodes which may be intersected by a ray. As can be seen in FIG. 1A, the technique represents an improvement compared to the conventional technique in which the entry point at the top node 110, as the entry point of the node traversal process is one rank lower at node 120, node 120 representing the common node for the primitive containing nodes 140, 150 and 160 which may be intersected by the ray.
FIG. 1B illustrates the tree structure when the primitive containing nodes are distributed a manner different from that shown in FIG. 1A. In particular, the root node 110 is identified as the best entry point, as it represents the common node for primitive containing, possibly intersected nodes 130, 140, 150 and 160. In such an instance, no benefit is gained from the disclosed improvement compared with the conventional approach, in which the root node 110 represents the entry point for node traversal.
Accordingly, what is needed is an improved method and system which provides more optimal entry points of a hierarchical structure.